﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Algoritmia.DataStructures.Maps;
using Algoritmia.Utils;

namespace Algoritmia.DataStructures.MergeFindSets
{
    public class NaiveMergeFindSet<T> : IMergeFindSet<T>
    {
        protected IMap<T, T> _parent;
        protected int _count;
        protected Func<IEnumerable<T>,IMap<T, T>> _createMap;
        protected Func<IEnumerable<T>,Lists.IList<T>> _createList;
        protected Func<IEnumerable<T>,IMap<T, Lists.IList<T>>> _createMapOfLists;
        protected EqualityComparison<T> _equalityComparison;

        public NaiveMergeFindSet(IEnumerable<IEnumerable<T>> sets=null, EqualityComparison<T> equalityComparison = null,
            Func<IEnumerable<T>,IMap<T,T>> createMap=null, Func<IEnumerable<T>,IMap<T,Lists.IList<T>>> createMapOfLists=null ,
            Func<IEnumerable<T>,Lists.IList<T>> createList=null)
        {
            sets = sets ?? Enumerable.Empty<IEnumerable<T>>();
            _equalityComparison = AlgoritmiaFactory.GetDefaultEqualityComparison(equalityComparison);
            _createMap = createMap ?? (items => AlgoritmiaFactory.Maps<T>.Default);
            _createList = createList ?? (items => AlgoritmiaFactory.Lists<T>.Default);
            _createMapOfLists = createMapOfLists ?? (items => AlgoritmiaFactory.Maps<T, Lists.IList<T>>.Default);


            sets = (from set in sets
                    select set.ToList()).ToList();

            IEnumerable<T> all = Enumerable.Empty<T>();

            foreach (var set in sets)
            {
                all.Concat(set);
            }
            _parent = _createMap(all);
            _count = 0;
            foreach (var set in sets)
            {
                List<T> list = set.ToList();
                if (list.Count > 0)
                {
                    _count++;
                    T first = list[0];
                    _parent[first] = first;
                    for (var i = 1; i < list.Count; i++)
                    {
                        _parent[list[i]] = first;
                    }
                }
            }
            
        }

        #region IMergeFindSet<T> Members

        public virtual void Add(T item)
        {
            _parent[item] = item;
            _count++;
        }

        public virtual void Merge(T item1, T item2)
        {
            T u = Find(item1);
            T v = Find(item2);
            if (!_equalityComparison(u,v))
            {
                _parent[v] = u;
                _count--;
            }
        }

        public virtual T Find(T item)
        {
            T aux = _parent[item];
            while (!_equalityComparison(aux,_parent[aux]))
            {
                aux = _parent[aux];
            }
            return aux;
        }

        #endregion

        #region IEnumerable<IEnumerable<T>> Members

        public IEnumerator<IEnumerable<T>> GetEnumerator()
        {
            var tmpMap = _createMapOfLists(_parent.Keys());
            foreach (T key in _parent.Keys())
            {
                tmpMap.SetDefault(Find(key), _createList(_parent.Keys())).Add(key);
            }
            foreach (var item in tmpMap.Values())
            {
                yield return item;
            }
        }

        #endregion

        #region IEnumerable Members

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        #endregion

        #region ICountable Members

        public int Count
        {
            get { return _count; }
        }

        #endregion

        public override string ToString()
        {
            StringBuilder sb = new StringBuilder(String.Format("{0} <{1}> [", GetType().Name, typeof(T).Name));
            foreach (var family in this)
            {
                sb.Append(String.Format("[{0}]", string.Join(",", family)));
            }
            sb.Append(" ]");
            return sb.ToString();
        }
    }
}
